package com.xiaoyg.algorithm;

import org.assertj.core.util.Lists;

import java.util.List;

public class FindDisappearedNumbers {

    public static void main(String[] args) {
        int []nums = {4,3,2,7,8,2,3,1};
        List<Integer> results = findDisappearedNumbers1(nums);
        for (Integer result : results) {
            System.out.println(result);
        }
    }

    public static List<Integer> findDisappearedNumbers(int []nums){
        //数组中所有元素都是数组[1,nums.length]的数据。有重复的数据，把每个元素的值-1在数组中都能找到下标
        //不包含所有的值，说明肯定有相同的数字。就将数组中所有的对应下标变成负数。最后不为负数的下标加1就是丢失的数字
        List<Integer> result = Lists.newArrayList();
        //循环处理下标
        for(int i = 0;i<nums.length;i++){
            int index = Math.abs(nums[i]);
            nums[index - 1] = Math.abs(nums[index - 1]) * -1;
        }
        //循环判断丢失的数字
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0){
                result.add(i + 1);
            }
        }
        return result;
    }




    public static List<Integer> findDisappearedNumbers1(int []nums){
        List<Integer> result = Lists.newArrayList();
        //获取数组长度
        int n = nums.length;
        /***
         * 1、必须将element-1对应的元素变成[1,n]以外的数字
         * 2、将对应的元素至少加一个n值
         *    1.加了n值肯定就大于数组的长度了，所以需要对n取模定位加n之后的下标
         * 3、最后没有加n值，即还在[1,n]之内的index+1就是消失的数字
         *    1.循环判断小于等于n的数+1
         */
        for (int num:nums) {
            //数字减1获取到下标
            int index = (num - 1)%n;
            nums[index] += n;
        }
        for (int i = 0;i< n;i++){
            if (nums[i] <= n){
                result.add(i + 1);
            }
        }
        return result;
    }
}
